Given a particular physical design for an integrated circuit, it is sometimes necessary to manipulate and modify elements of the circuit for any one or more of a variety of reasons, such as performing a scaling, an area compaction or a migration of one set of manufacturing design, or “ground,” rules to a different set of ground rules. Efficient techniques for performing such manipulations and modifications utilize a piecewise linear program (LP) and 2-variable difference and/or 2-variable sum constraints and objectives. Examples of such techniques are disclosed in U.S. Pat. No. 6,189,132, which is incorporated herein by reference. The principal requirement of any layout modification is that the resultant edge and usage locations must be integral, since the database underlying the physical design and the downstream fabrication tools require these locations to be represented by integers.
The presence of hierarchy in a design complicates the problem of layout optimization. In addition, designs in which elements appear in both mirrored and non-mirrored forms change the fundamental nature of the underlying optimization problem. In this case, the optimal solution to the LP might include half-integers. An arbitrary rounding of half integers to whole integers can potentially lead to an infeasible solution, i.e., a solution in which some of the constraints of the original problem are violated. In the context of layout optimization, these constraints encode connectivity information and ground rules already met in the layout. Consequently, arbitrary rounding in this context can produce a layout having electrical opens, shorts or ground-rule violations that did not exist in the layout.
In general, it is not possible to represent all of the desired relationships, i.e., objectives, as constraints and still obtain a feasible solution. In the presence of constraints and objectives, the rounding of a feasible half-integer solution to a feasible integer solution is a possibly non-satisfiable problem. The treatment of such a problem as an integer LP (ILP), in which all intermediate values in the optimization are kept as integers, is also an NP-complete problem and is not solvable in the sense that an optimal solution is guaranteed.
A typical migration using techniques disclosed in U.S. Pat. No. 6,189,132 involves scaling an entire layout from a source technology by some scale factor and then using an LP to fix any ground rule errors in the target technology according to the target technology's ground rules. For many edge relationships (for example metal to metal spacing) the relationship is ground rule correct in the target technology after the scaling has been applied. In this case a constraint is made so that this ground rule correct relationship cannot be broken. When a ground rule in the target technology is not met an objective is made. Constraints are also made for among other things electrical connectivity as stated above. Since every constraint in the LP is met by construction the initial layout before optimization represents a feasible integer solution.
It is quite possible that there is no solution to the LP that fixes all of the ground rule violations. However with the encoding of ground rules already met in the target technology as constraints no new ground rule errors can be introduced. An objective not met represents a ground rule that is not able to be fixed. Rounding must be done in such a way that a feasible solution is still guaranteed. This requires that no constraint be violated or in other words that no ground rule errors are introduced which would result in an infeasible solution to the LP.
When no feasible integer solution can be reached from the rational solution of an LP containing half-integers, which satisfies all the constraints and meets the same set of objectives; a near optimal integer result is still desired which leaves the layout as ground rule correct as possible. This greatly reduces the amount of manual effort required to get a layout ground-rule clean. Ground rule errors that result because of the restriction that the solution be integer can ultimately be fixed by manual efforts. Consequently, it would be desirable to have a technique for efficiently guaranteeing a feasible solution to such general linear programs and producing near-optimal integer solutions.